#include <vector>

using namespace std;
class Solution
{
    // 思路：以每一个元素作为子数组的结尾，计算以该元素结尾的最大子数组和
    // 如果前面的子数组和为负数，则不加上前面的子数组和
public:
    int maxSubArray(vector<int> &nums)
    {
        int res_max = nums[0]; // 结果最大值
        int cur_max = 0;       // 当前最大值
        // 以每一个元素作为子数组的结尾
        for (int i = 0; i < nums.size(); ++i)
        {
            // 如果当前元素的前面值为负数，则不加上前面的值
            if (cur_max < 0)
                cur_max = 0;
            cur_max += nums[i];
            res_max = max(res_max, cur_max);
        }
        return res_max;
    }
};